package leetcode.editor.cn;//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// 1 <= n <= 2 * 10⁴
// 0 <= height[i] <= 10⁵
//
//
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 5530 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int trap = solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        System.out.println(trap);
    }

    /**
     * 暴力方法
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length ; i++) {
            //计算右面的最大值
            int letmax = 0;
            for (int n = 0; n < i; n++) {
                letmax = Math.max(letmax, height[n]);
            }
            //计算左面的最大值
            int rightmax = 0;
            for (int n = i + 1; n < height.length; n++) {
                rightmax = Math.max(rightmax, height[n]);
            }
            //计算两者中的最小值
            int min = Math.min(letmax, rightmax);
            int i1 = min - height[i];
            i1 = i1 < 0 ? 0 : i1;
            sum += i1;


        }
        return sum;

    }

    /**
     * 优化方法
     *
     * @param height
     * @return
     */
    public int t1rap(int[] height) {
        int[] leftmaxarr = new int[height.length];
        int[] rightmaxarr = new int[height.length];
        //计算左边的最大值
        leftmaxarr[0] = 0;
        for (int i = 1; i < height.length; i++) {
            leftmaxarr[i] = Math.max(height[i - 1], leftmaxarr[i - 1]);
        }
        //计算右边的最大值
        rightmaxarr[height.length - 1] = 0;
        for (int i = height.length - 2; i >= 0; i--) {
            rightmaxarr[i] = Math.max(height[i +1], rightmaxarr[i + 1]);
        }
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            //计算右面的最大值
            int letmax = leftmaxarr[i];
            //计算左面的最大值
            int rightmax = rightmaxarr[i];
            //计算两者中的最小值
            int min = Math.min(letmax, rightmax);
            int i1 = min - height[i];
            i1 = i1 < 0 ? 0 : i1;
            sum += i1;


        }
        return sum;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
